package com.wz.leetcode.string;

import com.sun.scenario.effect.Brightpass;

import java.util.*;

public class ReverseWords_151 {
    public static String reverseWords(String s) {
        s = s.trim();
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }

    public static String reverseWords1(String s) {
        StringBuilder sb = trimSpaces(s);
        reverse(sb, 0, sb.length() - 1);
        reverseEachWord(sb);
        return sb.toString();
    }

    public static String reverseWords2(String s) {
        int left = 0;
        int right = s.length() - 1;
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }

        Deque<String> stack = new ArrayDeque<>();
        StringBuilder word = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ') {
                word.append(c);
            } else if (word.length() != 0) {
                stack.push(word.toString());
                word.setLength(0);
            }
            ++left;
        }
        stack.push(word.toString());
        return String.join(" ", stack);
    }

    private static void reverseEachWord(StringBuilder sb) {
        int n = sb.length();
        int start = 0;
        int end = 0;
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                ++end;
            }
            reverse(sb, start, end - 1);
            start = end + 1;
            ++end;
        }
    }

    private static void reverse(StringBuilder sb, int i, int j) {
        while (i < j) {
            char tmp = sb.charAt(i);
            sb.setCharAt(i++, sb.charAt(j));
            sb.setCharAt(j--, tmp);
        }
    }

    private static StringBuilder trimSpaces(String s) {
        int left = 0, right = s.length() - 1;
        while (left <= right && s.charAt(left) == ' ') {
            ++left;
        }
        while (left <= right && s.charAt(right) == ' ') {
            --right;
        }
        StringBuilder sb = new StringBuilder();
        while(left <= right) {
            char c = s.charAt(left);
            if (c != ' ') {
                sb.append(c);
            } else if (sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            ++left;
        }
        return sb;
    }

    public static void main(String[] args) {
        String str = "the sky is blue";
        System.out.println("\"" + str + "\" to \"" + reverseWords(str) + "\"");
        str = "  hello world  ";
        System.out.println("\"" + str + "\" to \"" + reverseWords(str) + "\"");
        str = "a good   example";
        System.out.println("\"" + str + "\" to \"" + reverseWords(str) + "\"");
        System.out.println("======================================");


        str = "the sky is blue";
        System.out.println("\"" + str + "\" to \"" + reverseWords1(str) + "\"");
        str = "  hello world  ";
        System.out.println("\"" + str + "\" to \"" + reverseWords1(str) + "\"");
        str = "a good   example";
        System.out.println("\"" + str + "\" to \"" + reverseWords1(str) + "\"");
        System.out.println("======================================");


        str = "the sky is blue";
        System.out.println("\"" + str + "\" to \"" + reverseWords2(str) + "\"");
        str = "  hello world  ";
        System.out.println("\"" + str + "\" to \"" + reverseWords2(str) + "\"");
        str = "a good   example";
        System.out.println("\"" + str + "\" to \"" + reverseWords2(str) + "\"");
    }
}
